package assignment03;

import java.util.ArrayList;
import java.util.List;

import nlp.util.Counter;

import assignment03.POSTaggerTester.Trellis;
import assignment03.POSTaggerTester.TrellisDecoder;

public class ViterbiDecoder<S> implements TrellisDecoder<S> {

	@Override
	public List<S> getBestPath(Trellis<S> trellis) {
		List<S> states = new ArrayList<S>();
		S currentState = trellis.getStartState();
		states.add(currentState);
		S previousMax = currentState;
		while (!currentState.equals(trellis.getEndState())) {
			Counter<S> forwardTransitions = trellis.getForwardTransitions(currentState);
			double max = Double.POSITIVE_INFINITY;//NEGATIVE_INFINITY;
			for (S nextState : forwardTransitions.keySet()) {
//				previousMax = nextState;
				Counter<S> backwardTransitions = trellis.getBackwardTransitions(nextState);
				for (S previousState: backwardTransitions.keySet()) {
					if (backwardTransitions.getCount(previousState) < max) {
						max = backwardTransitions.getCount(previousState);
						previousMax = previousState;
					}
				}
			}
//			if (nextMax.equals(trellis.getEndState())) {
//				System.out.println("end!");
//			} else {
//				System.out.println("not end");
//			}
			if (!states.contains(previousMax)) {
				states.add(previousMax);
			}
			currentState = forwardTransitions.argMax();
		}
		System.out.println("yeah");
		states.add(trellis.getEndState());
		return states;
	}

}
